import java.util.Stack;

public class code02 {
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flgLeft = getPath(root.left,node,stack);
        if(flgLeft) {
            return true;
        }
        boolean flgRight = getPath(root.right,node,stack);
        if(flgRight) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null) return null;
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1>size2) {
            int size = size1-size2;
            while(size--!=0){
                stack1.pop();
                size1--;
            }
        } else {
            int size = size2-size1;
            while(size!=0){
                stack2.pop();
                size2--;
            }
        }
        while(!stack1.isEmpty()&&!stack2.isEmpty()) {
            if(stack1.peek().equals(stack2.peek())) {
                return stack1.pop();
            } else {
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
}
